SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>AC-3 algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">AC-3 algorithm</span></span>

</h1>

</header>

<p>In <a href="Constraint_satisfaction" title="Constraint satisfaction">constraint satisfaction</a>, the <b>AC-3 algorithm</b> (short for <a href="Arc_consistency" class="mw-redirect" title="Arc consistency">Arc Consistency</a> Algorithm #3) is one of a series of <a href="Algorithm" title="Algorithm">algorithms</a> used for the solution of <a href="Constraint_satisfaction_problem" title="Constraint satisfaction problem">constraint satisfaction problems</a> (or CSPs). It was developed by <a href="Alan_Mackworth" title="Alan Mackworth">Alan Mackworth</a> in 1977. The earlier AC algorithms are often considered too inefficient, and many of the later ones are difficult to implement, and so AC-3 is the one most often taught and used in very simple constraint solvers. The AC-3 algorithm is not to be confused with the similarly named A3C algorithm in machine learning.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="The_algorithm">The algorithm</h2></div>

<p>AC-3 operates on <a href="Constraint_(mathematics)" title="Constraint (mathematics)">constraints</a>, <a href="Variable_(mathematics)" title="Variable (mathematics)">variables</a>, and the variables' domains (scopes). A <b>variable</b> can take any of several discrete values; the set of values for a particular variable is known as its <b>domain</b>. A <b>constraint</b> is a <a href="Relation_(mathematics)" title="Relation (mathematics)">relation</a> that limits or constrains the values a variable may have. The constraint may involve the values of other variables.

</p><p>The current status of the CSP during the algorithm can be viewed as a <a href="Directed_graph" title="Directed graph">directed graph</a>, where the nodes are the variables of the problem, with edges or arcs between variables that are related by symmetric constraints, where each arc in the worklist represents a constraint that needs to be checked for <a href="Arc_consistency" class="mw-redirect" title="Arc consistency">consistency</a>. AC-3 proceeds by examining the arcs between pairs of variables (<i>x</i>, <i>y</i>). It removes those values from the domain of <i>x</i> that aren't consistent with the constraints between <i>x</i> and <i>y</i>. The algorithm keeps a collection of arcs that are yet to be checked; when the domain of a variable has any values removed, all the arcs of constraints pointing to that pruned variable (except the arc of the current constraint) are added to the collection. Since the domains of the variables are finite and either one arc or at least one value are removed at each step, this algorithm is guaranteed to <a href="Termination_analysis" title="Termination analysis">terminate</a>.

</p><p>For illustration, here is an example of a very simple constraint problem:

<i>X</i> (a variable) has the possible values {0, 1, 2, 3, 4, 5}—the set of these values are the domain of <i>X</i>, or D(<i>X</i>). The variable <i>Y</i> has the domain D(<i>Y</i>) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Together with the constraints <i>C1</i> = "<i>X</i> must be even" and <i>C2</i> = "<i>X</i> + <i>Y</i> must equal 4" we have a CSP that AC-3 can solve. Notice that the actual constraint graph representing this problem must contain two edges between <i>X</i> and <i>Y</i> since <i>C2</i> is undirected but the graph representation being used by AC-3 is directed.

</p><p>AC-3 solves the problem by first removing the non-even values from of the domain of <i>X</i> as required by <i>C1</i>, leaving D(<i>X</i>) = { 0, 2, 4 }. It then examines the arcs between <i>X</i> and <i>Y</i> implied by <i>C2</i>. Only the pairs (<i>X</i>=0, <i>Y</i>=4), (<i>X</i>=2, <i>Y</i>=2), and (<i>X</i>=4, <i>Y</i>=0) match the constraint <i>C2</i>. AC-3 then terminates, with D(<i>X</i>) = {0, 2, 4} and D(<i>Y</i>) = {0, 2, 4}.

</p><p>AC-3 is expressed in pseudocode as follows:

</p>

<pre> <b>Input:</b>

A set of <a href="Variable_(mathematics)" title="Variable (mathematics)">variables</a> X

A set of <a href="Domain_of_a_function" title="Domain of a function">domains</a> D(x) for each variable x in X. D(x) contains vx0, vx1... vxn, the possible values of x

A set of unary constraints R1(x) on variable x that must be satisfied

A set of binary constraints R2(x, y) on variables x and y that must be satisfied

<b>Output:</b>

Arc consistent domains for each variable.

<b>function</b> ac3(X, D, R1, R2)

<i>// Initial domains are made consistent with unary constraints.</i>

<b>for each</b> x <b>in</b> X

D(x) := { vx in D(x) | vx satisfies R1(x) }

<i>// 'worklist' contains all arcs we wish to prove consistent or not.</i>

worklist := { (x, y) | there exists a relation R2(x, y) or a relation R2(y, x) }

select any arc (x, y) from worklist

worklist := worklist - (x, y)

<b>if</b> arc-reduce (x, y)

<b>if</b> D(x) is empty

<b>return</b> failure

worklist := worklist + { (z, x) | z != y and there exists a relation R2(x, z) or a relation R2(z, x) }

<b>while</b> worklist <b>not</b> empty

<b>function</b> arc-reduce(x, y)

<b>bool</b> change = <b>false</b>

<b>for each</b> vx <b>in</b> D(x)

find a value vy in D(y) such that vx and vy satisfy the constraint R2(x, y)

<b>if</b> there is no such vy {

D(x) := D(x) - vx

change := <b>true</b>

}

<b>return</b> change

</pre>

<p>The algorithm has a worst-case <a href="Time_complexity" title="Time complexity">time complexity</a> of <b><a href="Big_O_notation" title="Big O notation">O</a></b>(<i>ed<sup>3</sup></i>) and <a href="Space_complexity" title="Space complexity">space complexity</a> of <b><a href="Big_O_notation" title="Big O notation">O</a></b>(<i>e</i>), where <i>e</i> is the number of arcs and <i>d</i> is the size of the largest domain.

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFMinh2016" class="citation arxiv cs1">Minh, Volodymyr (16 Jun 2016). "Asynchronous Methods for Deep Reinforcement Learning". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/gr-qc/0610068">gr-qc/0610068</a></span>.</cite></span>

</li>

</ol></div></div>

<ul><li>A.K. Mackworth. <a rel="nofollow" class="external text" href="https://www.sciencedirect.com/science/article/abs/pii/0004370277900078">Consistency in networks of relations</a>. <i><a href="Artificial_Intelligence_(journal)" title="Artificial Intelligence (journal)">Artificial Intelligence</a></i>, 8:99-118, 1977.</li>

<li><a href="Stuart_J._Russell" title="Stuart J. Russell">Stuart J. Russell</a> and <a href="Peter_Norvig" title="Peter Norvig">Peter Norvig</a>. <i><a href="Artificial_Intelligence%3A_A_Modern_Approach" title="Artificial Intelligence: A Modern Approach">Artificial Intelligence: A Modern Approach</a></i>, 202-233, 2003.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-01-08" href="https://en.wikipedia.org/wiki/?title=AC-3_algorithm&oldid=1268163297">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>